C++语言题解
P党再见
看见标签:DP,想DP我不会这样发不了题解,于是有以下思路
思路:最大差值……差值!(划重点)差值怎么办呢?当然是用差分了!
懂了的退出自己想想。
差分,具体怎么办呢?最大差值,即找出差分数组的最大子段和。特别地,这里差分数组第一个位置要置成非正数(因为不能取第一个数前面隐藏的0),否则样例会过不了。
样例解释
| 类型 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 原数组 | 1 | 3 | 4 | 6 | 7 | 9 | 10 | 1 | 2 | 9 |
| 差分 | -1000000 | 2 | 1 | 2 | 1 | 2 | 1 | -9 | 1 | 7 |
| 最大子段和 | * | * | * | * | * | * |
最大子段和为d[1]+d[2]+d[3]+d[4]+d[5]+d[6],换回原数组即为a[1]-a[0]+a[2]-a[1]+a[3]-a[2]+a[4]-a[3]+a[5]-a[4]+a[6]-a[5],即a[6]-a[0],为最大差值。
代码:
#include <iostream>
#include <limits.h>
using namespace std;
int n, a[1000001], d[1000001], f[1000001];
int maxsum(void)
{
f[0] = d[0];
for(int i=1;i<n;i++) f[i] = max(f[i-1] + d[i], d[i]);
int m = INT_MIN;
for(int i=0;i<n;i++) m = max(m, f[i]);
return m;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
d[i] = i ? (a[i] - a[i-1]) : -1000000;//差分
}
// for(int i=0;i<n;i++) cout<<d[i]<<" ";
// cout<<endl;
cout<<maxsum()<<endl;
return 0;
}